package com.fitc.treestructure;

/*
 * Copyright (C) 2007-2012 by Brett Alistair Kromkamp <brett@polishedcode.com>.
 */

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;

public class DepthFirstTreeIterator implements Iterator<Node> {

    private static final int ROOT = 0;

    private LinkedList<Node> _queue;

    public DepthFirstTreeIterator(ArrayList<Node> tree) {
        _queue = new LinkedList<Node>();
        this.buildQueue(tree, ROOT);
    }

    /*
       See URL:

       1. http://en.wikipedia.org/wiki/Depth-first_search
    */
    private void buildQueue(ArrayList<Node> tree, int index) {
        _queue.add(tree.get(index));
        ArrayList<Integer> forwardPointers = tree.get(index).getForwardPointers();
        for (Integer forwardPointer : forwardPointers) {
            
            // Recursive call.
            this.buildQueue(tree, forwardPointer);
        }
    }

    @Override
    public boolean hasNext() {
        return !_queue.isEmpty();
    }

    @Override
    public Node next() {
        return _queue.poll();
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

}
